/*-------------------------------------------------------------------------*/
/**
  @file		dllmacro.h
  @author	Renaud Wanschoor
  @date	july 2004
  @version	$Revision: 2.4 $
  @brief	contains macros for dll

  plib functions are used to serialize matchings sequences and results of each
  level of the uncoarsening stage. They are currently used for METIS and PaGrid
  pagridplot also used plib functions.

  there are also utilities used by pagrid in plib, those are error handling,
  memory allocation, priority queues, randum number generator, dll as macros
  in fact all utils that may used for other programs.

  dllmacros are macros that allow the use of a double linked list inside an
  array of a typedef structure. This structure must have two members n for the next element
  and p for the previous element. The dll loops over the head, this means that the
  next element of the last element of the dll is the head. In pagrid dllmacros
  are used to implement dll inside containers of boundary vertices.

  DLL_ functions are used if all element of the array are within a dll
  DLA_ functions are used if some elements of the array are not within a dll
  AL_REM is a specific fonction used only by pagrid and it has nothing to do with
  dll (shouldn't be here i guess)

  Those macros are designed to keep the array compact when an element is added 
  or removed, this means that there are no hole in the array (no waste of memory
  at least between the first and last element of the array)
  
*/
/*--------------------------------------------------------------------------*/


#define DLL_START(head) (head)->n
#define DLA_START(head) DLL_START(head)
 
#define DLL_IS_END(head,elt) ((elt) == (head) ? 1 : 0)
#define DLA_IS_END(head,elt) DLL_IS_END(head,elt)

#define DLL_INIT(elt) (elt)->n = NULL;(elt)->p = NULL
#define DLA_INIT(elt) DLL_INIT(elt)

#define DLL_INIT_HEAD(head) (head)->n = (head);(head)->p = (head)
#define DLA_INIT_HEAD(head) DLL_INIT_HEAD(head)

#define DLL_NEXT(elt) (elt)->n
#define DLA_NEXT(elt) DLL_NEXT(elt)
#define DLL_PREV(elt) (elt)->p
#define DLA_PREV(elt) DLL_PREV(elt)

#define DLL_NEW(arr,size) ((arr)[(size)++])
#define DLA_NEW(arr,size) DLL_NEW(arr,size)

#define DLL_APPEND(head,arr,size){				\
  DLA_APPEND(head,(arr) + (size));				\
  (size)++;							\
}
#define DLA_APPEND(head,elt){					\
  (head)->p->n = (elt);						\
  (elt)->p     = (head)->p;					\
  (elt)->n     = (head);					\
  (head)->p    = (elt);						\
}

#define DLL_PUSH_NEW(head,arr,size){				\
  DLA_PUSH(head,(arr) + (size));				\
  (size)++;							\
}

#define DLA_PUSH(head,elt){					\
  (head)->n->p = (elt);						\
  (elt)->p     = (head);					\
  (elt)->n     = (head)->n;					\
  (head)->n    = (elt);						\
}

#define DLL_REM(elt,arr,size){					\
  (elt)->n->p = (elt)->p;					\
  (elt)->p->n = (elt)->n;					\
  if(((elt) - (arr)) != ((size) - 1)){				\
    *(elt) = (arr)[(size) - 1];					\
    (elt)->n->p = (elt);					\
    (elt)->p->n = (elt);					\
  }								\
  size--;							\
}

#define DLL_REM_UPDATE(elt,ptr,arr,size){			\
  (elt)->n->p = (elt)->p;					\
  (elt)->p->n = (elt)->n;					\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((ptr) == (arr) + ((size) - 1))				\
      (ptr) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    (elt)->n->p = (elt);					\
    (elt)->p->n = (elt);					\
  }								\
  size--;							\
}



#define DLA_REM(elt,arr,size){					\
  if((elt)->n != NULL){						\
    (elt)->n->p = (elt)->p;					\
    (elt)->p->n = (elt)->n;					\
  }								\
  if(((elt) - (arr)) != ((size) - 1)){				\
    *(elt) = (arr)[(size) - 1];					\
    if((elt)->n != NULL){					\
      (elt)->n->p = (elt);					\
      (elt)->p->n = (elt);					\
    }								\
  }								\
  size--;							\
}

#define AL_REM(elt,arr,size){					\
  (*(elt))->pos = NULL;						\
  if(((elt) - (arr)) != ((size) - 1)){				\
    *(elt) = (arr)[(size) - 1];					\
    (*(elt))->pos = (elt);					\
  }								\
  size--;							\
}

#define DLA_REM_UPDATE(elt,ptr,arr,size){			\
  if((elt)->n != NULL){						\
    (elt)->n->p = (elt)->p;					\
    (elt)->p->n = (elt)->n;					\
  }								\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((ptr) == (arr) + ((size) - 1))				\
      (ptr) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    if((elt)->n != NULL){					\
      (elt)->n->p = (elt);					\
      (elt)->p->n = (elt);					\
    }								\
  }								\
  size--;							\
}

#define DLL_REM_NEXT(elt,next,arr,size){			\
  (elt)->n->p = (elt)->p;					\
  (elt)->p->n = (next) = (elt)->n;				\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((next) == (arr) + ((size) - 1))				\
      (next) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    (elt)->n->p = (elt);					\
    (elt)->p->n = (elt);					\
  }								\
  (size)--;							\
}

#define DLA_REM_NEXT(elt,next,arr,size){			\
  if((elt)->n != NULL){						\
    (elt)->n->p = (elt)->p;					\
    (elt)->p->n = (next) = (elt)->n;				\
  }								\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((next) == (arr) + ((size) - 1))				\
      (next) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    if((elt)->n != NULL){					\
      (elt)->n->p = (elt);					\
      (elt)->p->n = (elt);					\
    }								\
  }								\
  (size)--;							\
}

#define DLL_REM_NEXT_UPDATE(elt,next,ptr,arr,size){		\
  (elt)->n->p = (elt)->p;					\
  (elt)->p->n = (next) = (elt)->n;				\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((ptr)  == (arr) + ((size) - 1))				\
      (ptr) = (elt);						\
    if((next) == (arr) + ((size) - 1))				\
      (next) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    (elt)->n->p = (elt);					\
    (elt)->p->n = (elt);					\
  }								\
  (size)--;							\
}

#define DLA_REM_NEXT_UPDATE(elt,next,ptr,arr,size){		\
  if((elt)->n != NULL){						\
    (elt)->n->p = (elt)->p;					\
    (elt)->p->n = (next) = (elt)->n;				\
  }								\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((ptr)  == (arr) + ((size) - 1))				\
      (ptr) = (elt);						\
    if((next) == (arr) + ((size) - 1))				\
      (next) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    if((elt)->n != NULL){					\
      (elt)->n->p = (elt);					\
      (elt)->p->n = (elt);					\
    }								\
  }								\
  (size)--;							\
}

#define DLL_REM_PREV(elt,prev,arr,size){			\
  (elt)->n->p = (prev) = (elt)->p;				\
  (elt)->p->n = (elt)->n;					\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((prev) == (arr) + ((size) - 1))				\
      (prev) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    (elt)->n->p = (elt);					\
    (elt)->p->n = (elt);					\
  }								\
  (size)--;							\
}

#define DLA_REM_PREV(elt,prev,arr,size){			\
  (elt)->n->p = (prev) = (elt)->p;				\
  (elt)->p->n = (elt)->n;					\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((prev) == (arr) + ((size) - 1))				\
      (prev) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    if((elt)->n != NULL){					\
      (elt)->n->p = (elt);					\
      (elt)->p->n = (elt);					\
    }								\
  }								\
  (size)--;							\
}

#define DLL_REM_PREV_UPDATE(elt,prev,ptr,arr,size){		\
  (elt)->n->p = (prev) = (elt)->p;				\
  (elt)->p->n = (elt)->n;					\
  if(((elt) - (arr)) != ((size) - 1)){				\
    if((ptr)  == (arr) + ((size) - 1))				\
      (ptr) = (elt);						\
    if((prev) == (arr) + ((size) - 1))				\
      (prev) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    (elt)->n->p = (elt);					\
    (elt)->p->n = (elt);					\
  }								\
  (size)--;							\
}

#define DLA_REM_PREV_UPDATE(elt,prev,ptr,arr,size){		\
  (elt)->n->p = (prev) = (elt)->p;				\
  (elt)->p->n = (elt)->n;					\
  if(((elt) - (arr)) != ((size) - 1)){				\
    DLL_DEBUG(((elt) - (arr)) > ((size) - 1),"C_prev_update size<pos");\
    if((ptr)  == (arr) + ((size) - 1))				\
      (ptr) = (elt);						\
    if((prev) == (arr) + ((size) - 1))				\
      (prev) = (elt);						\
    *(elt) = (arr)[(size) - 1];					\
    if((elt)->n != NULL){					\
      (elt)->n->p = (elt);					\
      (elt)->p->n = (elt);					\
    }	       							\
  }								\
  (size)--;							\
}

#define DLL_DEBUG(cond,msg){					\
  if(cond){							\
      printSeeds(ctrl);\
      ERROR((1,msg));\
  }\
}
